package oct2013;

/**
 * @author Yinzi Chen
 * @date Nov 15, 2013
 */
public class WordSearch {

    static final int[][] v = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 },
            { 0, -1 } };

    boolean[][] used;

    public boolean exist(char[][] board, String word) {
        if (word.length() == 0)
            return true;
        if (board.length == 0)
            return false;
        used = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (dfs(board, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }

    boolean dfs(char[][] board, int i, int j, String word, int dep) {
        if (dep == word.length()) {
            return true;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length
                || used[i][j] || board[i][j] != word.charAt(dep))
            return false;
        used[i][j] = true;
        for (int k = 0; k < 4; ++k) {
            int x = i + v[k][0], y = j + v[k][1];
            if (dfs(board, x, y, word, dep + 1)) {
                used[i][j] = false;
                return true;
            }
        }
        used[i][j] = false;
        return false;
    }
}
